1. (10 bodů) Na vstupu je dána posloupnost nul a jedniček. Navrhněte efektivní algoritmus, který v posloupnosti najde souvislý úsek, který obsahuje více jedniček než nul a rozdíl počtu jedniček a počtu nul je v něm maximální. Výsledkem algoritmu bude údaj, o kolik je v nalezeném úseku více jedniček než nul.
Navrhněte postup, jak správně vyřešit úlohu s co nejlepší časovou složitostí vzhledem k délce posloupnosti n. Budete-li používat nějakou pomocnou datovou strukturu, nezapomeňte popsat složitost operací nad ní prováděných.
(a) Popište algoritmus (včetně datových struktur, které případně budete používat). Programový kód není povinný, slovní vysvětlení zvoleného postupu řešení naopak povinné je.
(b) Zdůvodněte správnost algoritmu.
(c) Odvoďte asymptotickou časovou a prostorovou složitost (v nejhorším případě).
Příklad:
vstup: 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0
výstup: 3
2. (10 bodů) Je zadán binární strom, v jehož vrcholech jsou uložena celá čísla. Pojmem k-tá hladina stromu označíme množinu všech vrcholů ve vzdálenosti k od kořene. Kořen samotný leží v hladině 0. Navrhněte efektivní algoritmus, který vrátí číslo hladiny, která má maximální součet ohodnocení svých vrcholů.
(a) Svoje řešení zapište jako funkci v Pythonu, využijte definici třídy pro vrchol binárního stromu uvedenou níže a váš kód opatřete komentáři,
(b) zdůvodněte správnost,
(c) odvoďte časovou složitost.
class VrcholBinStromu:
"""třída pro reprezentaci vrcholu binárního stromu"""
def init(self, info = None, levy = None, pravy = None)
self.info = info # data
self.levy = levy # levé dítě
self.pravy = pravy # pravé dítě
def maxHladina(koren: VrcholBinStromu) -> int:
"""
koren : kořen zadaného binárního stromu
vrátí : číslo hladiny s maximálním součtem ohodnocení vrcholů
"""
3. Odpovězte na otázky.
(a) (5 bodů). Vstup: Minimalistická (v kořenu je minimum) binární halda uložená v poli, index jejího prvku p, nová hodnota h.
Výstup: Halda, v níž má prvek p novou hodnotu h.
Rozhodněte, zda platí:
Složitost operace změny hodnoty zadaného prvku v binární haldě o n prvcích je O(log n).
Svoji odpověď zdůvodněte, tj. tvrzení dokažte nebo vyvraťte. Nestačí jen napsat, že je to triviální či že to bylo na přednášce / cvičeních apod.
(b) (5 bodů) Jsou zadány dva aritmetické výrazy, první v prefixové, druhý v postfixové notaci:
(b1) - - 1 * * - 2 * 3 4 + 5 6 7 - 8 9
(b2) 1 2 3 4 5 * 6 + * - 7 * 8 - 9 - -
Ke každému z výrazů sestrojte příslušný strom aritmetického výrazu a poté vypište všechny hodnoty (čísla i znaménka) uložené v jeho vrcholech v pořadí, v němž budou navštíveny při průchodu stromem do šířky (děti každého vrcholu navštěvujeme v pořadí levé dítě, pravé dítě). Ve vaší odpovědi stačí vypsat hodnoty v požadovaném pořadí, nemusíte uvádět strom ani zdůvodnění.